package com.pandy.leetcode;

/**
 * @description: 二叉树的最近公关祖先
 *
 * https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/description/
 * @author: panhong
 * @date: 2025/4/2
 */
public class Code007_BinaryTree_PublicAncestors {

    public static BinaryTreeNode ancestors(BinaryTreeNode head, BinaryTreeNode a, BinaryTreeNode b) {
        return process(head, a, b).answer;
    }

    static class Info {
        private boolean isExistA;
        private boolean isExistB;
        private BinaryTreeNode answer;

        public Info(boolean isExistA, boolean isExistB, BinaryTreeNode answer) {
            this.isExistA = isExistA;
            this.isExistB = isExistB;
            this.answer = answer;
        }

        public BinaryTreeNode getAnswer() {
            return answer;
        }
    }

    public static Info process(BinaryTreeNode x, BinaryTreeNode a, BinaryTreeNode b) {
        if(x == null) {
            return new Info(false, false, null);
        }

        Info leftInfo = process(x.left, a, b);
        Info rightInfo = process(x.right, a, b);

        boolean isExistA = leftInfo.isExistA || rightInfo.isExistA || x == a;
        boolean isExistB = leftInfo.isExistB || rightInfo.isExistB || x == b;

        BinaryTreeNode answer = null;
        if(leftInfo.answer != null) {
            answer = leftInfo.answer;
        } else if(rightInfo.answer != null) {
            answer = rightInfo.answer;
        } else {
            if(isExistA && isExistB) {
                answer = x;
            }
        }

        return new Info(isExistA, isExistB, answer);
    }

    public static void main(String[] args) {
        int maxLevel = 4;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            BinaryTreeNode head = BinaryTreeRandomUtil.generateRandomBST(maxLevel, maxValue);
            BinaryTreeNode a = BinaryTreeRandomUtil.pickRandomOne(head);
            BinaryTreeNode b = BinaryTreeRandomUtil.pickRandomOne(head);
            BinaryTreeNode answer = ancestors(head, a, b);
            System.out.println(answer == null ? "没有最近公共祖先" : answer.value);
        }
        System.out.println("finish!");


    }
}
